// 给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

// 注意：请不要在超过该数组长度的位置写入元素。

// 要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

//  

// 示例 1：

// 输入：[1,0,2,3,0,4,5,0]
// 输出：null
// 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
// 示例 2：

// 输入：[1,2,3]
// 输出：null
// 解释：调用函数后，输入的数组将被修改为：[1,2,3]
//  

// 提示：

// 1 <= arr.length <= 10000
// 0 <= arr[i] <= 9

#include "stdc++.h"

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int possibleDups{0};
        int n = arr.size();
        int length = n - 1;
        // Find the number of zeros to be duplicated
        // Stopping when left points beyond the last element in the original array
        // which would be part of the modified array
        for (int left{0}; left <= length - possibleDups; ++left) {
            // count the zeros
            if (arr[left] == 0) {
                // Edge case: This zero can't be duplicated. We have no more space,
                // as left is pointing to the last element which could be included
                if (left == length - possibleDups) {
                    // for this zero we just copy it without duplication
                    arr[length] = 0;
                    length -= 1;
                    break;
                }
                ++possibleDups;
            }
        }
        // start backwards from the last element which would be part of new array
        int last = length - possibleDups;
        // copy zero twice and non zero once
        for (int i{last}; i >= 0; --i) {
            if (arr[i] == 0) {
                arr[i + possibleDups] = 0;
                --possibleDups;
                arr[i + possibleDups] = 0;
            } else {
                arr[i + possibleDups] = arr[i];
            }
        }
    }
};

// 双指针
class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        int i = -1;
        int top = 0;
        while (top < n) {
            ++i;
            if (arr[i] != 0) {
                top += 1;
            } else {
                top += 2;
            }
        }
        cout << i << endl;
        int j = n - 1;
        if (top == n + 1 ) {
            arr[j] = 0;
            --j;
            --i;
        }
        while (j >= 0) {
            arr[j] = arr[i];
            --j;
            if (arr[i] == 0) {
                arr[j] = 0;
                --j;
            }
            --i;
        }
    }
};

